<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">


<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    
    <title>django.utils.datastructures &mdash; Django 1.7.8.dev20150401230226 documentation</title>
    
    <link rel="stylesheet" href="../../../_static/default.css" type="text/css" />
    <link rel="stylesheet" href="../../../_static/pygments.css" type="text/css" />
    
    <script type="text/javascript">
      var DOCUMENTATION_OPTIONS = {
        URL_ROOT:    '../../../',
        VERSION:     '1.7.8.dev20150401230226',
        COLLAPSE_INDEX: false,
        FILE_SUFFIX: '.html',
        HAS_SOURCE:  true
      };
    </script>
    <script type="text/javascript" src="../../../_static/jquery.js"></script>
    <script type="text/javascript" src="../../../_static/underscore.js"></script>
    <script type="text/javascript" src="../../../_static/doctools.js"></script>
    <link rel="top" title="Django 1.7.8.dev20150401230226 documentation" href="../../../index.html" />
    <link rel="up" title="django" href="../../django.html" />



 
<script type="text/javascript" src="../../../templatebuiltins.js"></script>
<script type="text/javascript">
(function($) {
    if (!django_template_builtins) {
       // templatebuiltins.js missing, do nothing.
       return;
    }
    $(document).ready(function() {
        // Hyperlink Django template tags and filters
        var base = "../../../ref/templates/builtins.html";
        if (base == "#") {
            // Special case for builtins.html itself
            base = "";
        }
        // Tags are keywords, class '.k'
        $("div.highlight\\-html\\+django span.k").each(function(i, elem) {
             var tagname = $(elem).text();
             if ($.inArray(tagname, django_template_builtins.ttags) != -1) {
                 var fragment = tagname.replace(/_/, '-');
                 $(elem).html("<a href='" + base + "#" + fragment + "'>" + tagname + "</a>");
             }
        });
        // Filters are functions, class '.nf'
        $("div.highlight\\-html\\+django span.nf").each(function(i, elem) {
             var filtername = $(elem).text();
             if ($.inArray(filtername, django_template_builtins.tfilters) != -1) {
                 var fragment = filtername.replace(/_/, '-');
                 $(elem).html("<a href='" + base + "#" + fragment + "'>" + filtername + "</a>");
             }
        });
    });
})(jQuery);
</script>


  </head>
  <body>

    <div class="document">
  <div id="custom-doc" class="yui-t6">
    <div id="hd">
      <h1><a href="../../../index.html">Django 1.7.8.dev20150401230226 documentation</a></h1>
      <div id="global-nav">
        <a title="Home page" href="../../../index.html">Home</a>  |
        <a title="Table of contents" href="../../../contents.html">Table of contents</a>  |
        <a title="Global index" href="../../../genindex.html">Index</a>  |
        <a title="Module index" href="../../../py-modindex.html">Modules</a>
      </div>
      <div class="nav">
    <a href="../../index.html" title="Module code" accesskey="U">up</a></div>
    </div>

    <div id="bd">
      <div id="yui-main">
        <div class="yui-b">
          <div class="yui-g" id="_modules-django-utils-datastructures">
            
  <h1>Source code for django.utils.datastructures</h1><div class="highlight"><pre>
<span class="kn">import</span> <span class="nn">copy</span>
<span class="kn">import</span> <span class="nn">warnings</span>
<span class="kn">from</span> <span class="nn">collections</span> <span class="kn">import</span> <span class="n">OrderedDict</span>

<span class="kn">from</span> <span class="nn">django.utils</span> <span class="kn">import</span> <span class="n">six</span>
<span class="kn">from</span> <span class="nn">django.utils.deprecation</span> <span class="kn">import</span> <span class="n">RemovedInDjango19Warning</span>


<span class="k">class</span> <span class="nc">MergeDict</span><span class="p">(</span><span class="nb">object</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    A simple class for creating new &quot;virtual&quot; dictionaries that actually look</span>
<span class="sd">    up values in more than one dictionary, passed in the constructor.</span>

<span class="sd">    If a key appears in more than one of the given dictionaries, only the</span>
<span class="sd">    first occurrence will be used.</span>
<span class="sd">    &quot;&quot;&quot;</span>
    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="o">*</span><span class="n">dicts</span><span class="p">):</span>
        <span class="n">warnings</span><span class="o">.</span><span class="n">warn</span><span class="p">(</span><span class="s">&#39;`MergeDict` is deprecated, use `dict.update()` &#39;</span>
                      <span class="s">&#39;instead.&#39;</span><span class="p">,</span> <span class="n">RemovedInDjango19Warning</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">dicts</span> <span class="o">=</span> <span class="n">dicts</span>

    <span class="k">def</span> <span class="nf">__bool__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="nb">any</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">dicts</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">__nonzero__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="nb">type</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">__bool__</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">__getitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
        <span class="k">for</span> <span class="n">dict_</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">dicts</span><span class="p">:</span>
            <span class="k">try</span><span class="p">:</span>
                <span class="k">return</span> <span class="n">dict_</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
            <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
                <span class="k">pass</span>
        <span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">__copy__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">__class__</span><span class="p">(</span><span class="o">*</span><span class="bp">self</span><span class="o">.</span><span class="n">dicts</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">get</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">default</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
        <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
            <span class="k">return</span> <span class="n">default</span>

    <span class="c"># This is used by MergeDicts of MultiValueDicts.</span>
    <span class="k">def</span> <span class="nf">getlist</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
        <span class="k">for</span> <span class="n">dict_</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">dicts</span><span class="p">:</span>
            <span class="k">if</span> <span class="n">key</span> <span class="ow">in</span> <span class="n">dict_</span><span class="p">:</span>
                <span class="k">return</span> <span class="n">dict_</span><span class="o">.</span><span class="n">getlist</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>
        <span class="k">return</span> <span class="p">[]</span>

    <span class="k">def</span> <span class="nf">_iteritems</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="n">seen</span> <span class="o">=</span> <span class="nb">set</span><span class="p">()</span>
        <span class="k">for</span> <span class="n">dict_</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">dicts</span><span class="p">:</span>
            <span class="k">for</span> <span class="n">item</span> <span class="ow">in</span> <span class="n">six</span><span class="o">.</span><span class="n">iteritems</span><span class="p">(</span><span class="n">dict_</span><span class="p">):</span>
                <span class="n">k</span> <span class="o">=</span> <span class="n">item</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
                <span class="k">if</span> <span class="n">k</span> <span class="ow">in</span> <span class="n">seen</span><span class="p">:</span>
                    <span class="k">continue</span>
                <span class="n">seen</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">k</span><span class="p">)</span>
                <span class="k">yield</span> <span class="n">item</span>

    <span class="k">def</span> <span class="nf">_iterkeys</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">for</span> <span class="n">k</span><span class="p">,</span> <span class="n">v</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">_iteritems</span><span class="p">():</span>
            <span class="k">yield</span> <span class="n">k</span>

    <span class="k">def</span> <span class="nf">_itervalues</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">for</span> <span class="n">k</span><span class="p">,</span> <span class="n">v</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">_iteritems</span><span class="p">():</span>
            <span class="k">yield</span> <span class="n">v</span>

    <span class="k">if</span> <span class="n">six</span><span class="o">.</span><span class="n">PY3</span><span class="p">:</span>
        <span class="n">items</span> <span class="o">=</span> <span class="n">_iteritems</span>
        <span class="n">keys</span> <span class="o">=</span> <span class="n">_iterkeys</span>
        <span class="n">values</span> <span class="o">=</span> <span class="n">_itervalues</span>
    <span class="k">else</span><span class="p">:</span>
        <span class="n">iteritems</span> <span class="o">=</span> <span class="n">_iteritems</span>
        <span class="n">iterkeys</span> <span class="o">=</span> <span class="n">_iterkeys</span>
        <span class="n">itervalues</span> <span class="o">=</span> <span class="n">_itervalues</span>

        <span class="k">def</span> <span class="nf">items</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
            <span class="k">return</span> <span class="nb">list</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">iteritems</span><span class="p">())</span>

        <span class="k">def</span> <span class="nf">keys</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
            <span class="k">return</span> <span class="nb">list</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">iterkeys</span><span class="p">())</span>

        <span class="k">def</span> <span class="nf">values</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
            <span class="k">return</span> <span class="nb">list</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">itervalues</span><span class="p">())</span>

    <span class="k">def</span> <span class="nf">has_key</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
        <span class="k">for</span> <span class="n">dict_</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">dicts</span><span class="p">:</span>
            <span class="k">if</span> <span class="n">key</span> <span class="ow">in</span> <span class="n">dict_</span><span class="p">:</span>
                <span class="k">return</span> <span class="bp">True</span>
        <span class="k">return</span> <span class="bp">False</span>

    <span class="n">__contains__</span> <span class="o">=</span> <span class="n">has_key</span>

    <span class="n">__iter__</span> <span class="o">=</span> <span class="n">_iterkeys</span>

    <span class="k">def</span> <span class="nf">copy</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Returns a copy of this object.&quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">__copy__</span><span class="p">()</span>

    <span class="k">def</span> <span class="nf">__str__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;</span>
<span class="sd">        Returns something like</span>

<span class="sd">            &quot;{&#39;key1&#39;: &#39;val1&#39;, &#39;key2&#39;: &#39;val2&#39;, &#39;key3&#39;: &#39;val3&#39;}&quot;</span>

<span class="sd">        instead of the generic &quot;&lt;object meta-data&gt;&quot; inherited from object.</span>
<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">return</span> <span class="nb">str</span><span class="p">(</span><span class="nb">dict</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">()))</span>

    <span class="k">def</span> <span class="nf">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;</span>
<span class="sd">        Returns something like</span>

<span class="sd">            MergeDict({&#39;key1&#39;: &#39;val1&#39;, &#39;key2&#39;: &#39;val2&#39;}, {&#39;key3&#39;: &#39;val3&#39;})</span>

<span class="sd">        instead of generic &quot;&lt;object meta-data&gt;&quot; inherited from object.</span>
<span class="sd">        &#39;&#39;&#39;</span>
        <span class="n">dictreprs</span> <span class="o">=</span> <span class="s">&#39;, &#39;</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="nb">repr</span><span class="p">(</span><span class="n">d</span><span class="p">)</span> <span class="k">for</span> <span class="n">d</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">dicts</span><span class="p">)</span>
        <span class="k">return</span> <span class="s">&#39;</span><span class="si">%s</span><span class="s">(</span><span class="si">%s</span><span class="s">)&#39;</span> <span class="o">%</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">__class__</span><span class="o">.</span><span class="n">__name__</span><span class="p">,</span> <span class="n">dictreprs</span><span class="p">)</span>


<div class="viewcode-block" id="SortedDict"><a class="viewcode-back" href="../../../ref/utils.html#django.utils.datastructures.SortedDict">[docs]</a><span class="k">class</span> <span class="nc">SortedDict</span><span class="p">(</span><span class="nb">dict</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    A dictionary that keeps its keys in the order in which they&#39;re inserted.</span>
<span class="sd">    &quot;&quot;&quot;</span>
    <span class="k">def</span> <span class="nf">__new__</span><span class="p">(</span><span class="n">cls</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
        <span class="n">instance</span> <span class="o">=</span> <span class="nb">super</span><span class="p">(</span><span class="n">SortedDict</span><span class="p">,</span> <span class="n">cls</span><span class="p">)</span><span class="o">.</span><span class="n">__new__</span><span class="p">(</span><span class="n">cls</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">)</span>
        <span class="n">instance</span><span class="o">.</span><span class="n">keyOrder</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="k">return</span> <span class="n">instance</span>

    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">data</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
        <span class="n">warnings</span><span class="o">.</span><span class="n">warn</span><span class="p">(</span>
            <span class="s">&quot;SortedDict is deprecated and will be removed in Django 1.9.&quot;</span><span class="p">,</span>
            <span class="n">RemovedInDjango19Warning</span><span class="p">,</span> <span class="n">stacklevel</span><span class="o">=</span><span class="mi">2</span>
        <span class="p">)</span>
        <span class="k">if</span> <span class="n">data</span> <span class="ow">is</span> <span class="bp">None</span> <span class="ow">or</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">data</span><span class="p">,</span> <span class="nb">dict</span><span class="p">):</span>
            <span class="n">data</span> <span class="o">=</span> <span class="n">data</span> <span class="ow">or</span> <span class="p">[]</span>
            <span class="nb">super</span><span class="p">(</span><span class="n">SortedDict</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">__init__</span><span class="p">(</span><span class="n">data</span><span class="p">)</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">keyOrder</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">data</span><span class="p">)</span> <span class="k">if</span> <span class="n">data</span> <span class="k">else</span> <span class="p">[]</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="nb">super</span><span class="p">(</span><span class="n">SortedDict</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">__init__</span><span class="p">()</span>
            <span class="n">super_set</span> <span class="o">=</span> <span class="nb">super</span><span class="p">(</span><span class="n">SortedDict</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">__setitem__</span>
            <span class="k">for</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span> <span class="ow">in</span> <span class="n">data</span><span class="p">:</span>
                <span class="c"># Take the ordering from first key</span>
                <span class="k">if</span> <span class="n">key</span> <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
                    <span class="bp">self</span><span class="o">.</span><span class="n">keyOrder</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>
                <span class="c"># But override with last value in data (dict() does this)</span>
                <span class="n">super_set</span><span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="n">value</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">__deepcopy__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">memo</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">__class__</span><span class="p">([(</span><span class="n">key</span><span class="p">,</span> <span class="n">copy</span><span class="o">.</span><span class="n">deepcopy</span><span class="p">(</span><span class="n">value</span><span class="p">,</span> <span class="n">memo</span><span class="p">))</span>
                               <span class="k">for</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">()])</span>

    <span class="k">def</span> <span class="nf">__copy__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="c"># The Python&#39;s default copy implementation will alter the state</span>
        <span class="c"># of self. The reason for this seems complex but is likely related to</span>
        <span class="c"># subclassing dict.</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">copy</span><span class="p">()</span>

    <span class="k">def</span> <span class="nf">__setitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span><span class="p">):</span>
        <span class="k">if</span> <span class="n">key</span> <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">keyOrder</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>
        <span class="nb">super</span><span class="p">(</span><span class="n">SortedDict</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">__setitem__</span><span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="n">value</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">__delitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
        <span class="nb">super</span><span class="p">(</span><span class="n">SortedDict</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">__delitem__</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">keyOrder</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">__iter__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="nb">iter</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">keyOrder</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">__reversed__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="nb">reversed</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">keyOrder</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">pop</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">k</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">):</span>
        <span class="n">result</span> <span class="o">=</span> <span class="nb">super</span><span class="p">(</span><span class="n">SortedDict</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="n">k</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">)</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">keyOrder</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="n">k</span><span class="p">)</span>
        <span class="k">except</span> <span class="ne">ValueError</span><span class="p">:</span>
            <span class="c"># Key wasn&#39;t in the dictionary in the first place. No problem.</span>
            <span class="k">pass</span>
        <span class="k">return</span> <span class="n">result</span>

    <span class="k">def</span> <span class="nf">popitem</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="n">result</span> <span class="o">=</span> <span class="nb">super</span><span class="p">(</span><span class="n">SortedDict</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">popitem</span><span class="p">()</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">keyOrder</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="n">result</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span>
        <span class="k">return</span> <span class="n">result</span>

    <span class="k">def</span> <span class="nf">_iteritems</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">for</span> <span class="n">key</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">keyOrder</span><span class="p">:</span>
            <span class="k">yield</span> <span class="n">key</span><span class="p">,</span> <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>

    <span class="k">def</span> <span class="nf">_iterkeys</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">for</span> <span class="n">key</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">keyOrder</span><span class="p">:</span>
            <span class="k">yield</span> <span class="n">key</span>

    <span class="k">def</span> <span class="nf">_itervalues</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">for</span> <span class="n">key</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">keyOrder</span><span class="p">:</span>
            <span class="k">yield</span> <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>

    <span class="k">if</span> <span class="n">six</span><span class="o">.</span><span class="n">PY3</span><span class="p">:</span>
        <span class="n">items</span> <span class="o">=</span> <span class="n">_iteritems</span>
        <span class="n">keys</span> <span class="o">=</span> <span class="n">_iterkeys</span>
        <span class="n">values</span> <span class="o">=</span> <span class="n">_itervalues</span>
    <span class="k">else</span><span class="p">:</span>
        <span class="n">iteritems</span> <span class="o">=</span> <span class="n">_iteritems</span>
        <span class="n">iterkeys</span> <span class="o">=</span> <span class="n">_iterkeys</span>
        <span class="n">itervalues</span> <span class="o">=</span> <span class="n">_itervalues</span>

        <span class="k">def</span> <span class="nf">items</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
            <span class="k">return</span> <span class="p">[(</span><span class="n">k</span><span class="p">,</span> <span class="bp">self</span><span class="p">[</span><span class="n">k</span><span class="p">])</span> <span class="k">for</span> <span class="n">k</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">keyOrder</span><span class="p">]</span>

        <span class="k">def</span> <span class="nf">keys</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">keyOrder</span><span class="p">[:]</span>

        <span class="k">def</span> <span class="nf">values</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
            <span class="k">return</span> <span class="p">[</span><span class="bp">self</span><span class="p">[</span><span class="n">k</span><span class="p">]</span> <span class="k">for</span> <span class="n">k</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">keyOrder</span><span class="p">]</span>

    <span class="k">def</span> <span class="nf">update</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">dict_</span><span class="p">):</span>
        <span class="k">for</span> <span class="n">k</span><span class="p">,</span> <span class="n">v</span> <span class="ow">in</span> <span class="n">six</span><span class="o">.</span><span class="n">iteritems</span><span class="p">(</span><span class="n">dict_</span><span class="p">):</span>
            <span class="bp">self</span><span class="p">[</span><span class="n">k</span><span class="p">]</span> <span class="o">=</span> <span class="n">v</span>

    <span class="k">def</span> <span class="nf">setdefault</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">default</span><span class="p">):</span>
        <span class="k">if</span> <span class="n">key</span> <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">keyOrder</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>
        <span class="k">return</span> <span class="nb">super</span><span class="p">(</span><span class="n">SortedDict</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">setdefault</span><span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="n">default</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">copy</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Returns a copy of this object.&quot;&quot;&quot;</span>
        <span class="c"># This way of initializing the copy means it works for subclasses, too.</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">__class__</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Replaces the normal dict.__repr__ with a version that returns the keys</span>
<span class="sd">        in their sorted order.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="s">&#39;{</span><span class="si">%s</span><span class="s">}&#39;</span> <span class="o">%</span> <span class="s">&#39;, &#39;</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="s">&#39;</span><span class="si">%r</span><span class="s">: </span><span class="si">%r</span><span class="s">&#39;</span> <span class="o">%</span> <span class="p">(</span><span class="n">k</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span> <span class="k">for</span> <span class="n">k</span><span class="p">,</span> <span class="n">v</span> <span class="ow">in</span> <span class="n">six</span><span class="o">.</span><span class="n">iteritems</span><span class="p">(</span><span class="bp">self</span><span class="p">))</span>

    <span class="k">def</span> <span class="nf">clear</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="nb">super</span><span class="p">(</span><span class="n">SortedDict</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">clear</span><span class="p">()</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">keyOrder</span> <span class="o">=</span> <span class="p">[]</span>

</div>
<span class="k">class</span> <span class="nc">OrderedSet</span><span class="p">(</span><span class="nb">object</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    A set which keeps the ordering of the inserted items.</span>
<span class="sd">    Currently backs onto OrderedDict.</span>
<span class="sd">    &quot;&quot;&quot;</span>

    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">iterable</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">dict</span> <span class="o">=</span> <span class="n">OrderedDict</span><span class="p">(((</span><span class="n">x</span><span class="p">,</span> <span class="bp">None</span><span class="p">)</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">iterable</span><span class="p">)</span> <span class="k">if</span> <span class="n">iterable</span> <span class="k">else</span> <span class="p">[])</span>

    <span class="k">def</span> <span class="nf">add</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">dict</span><span class="p">[</span><span class="n">item</span><span class="p">]</span> <span class="o">=</span> <span class="bp">None</span>

    <span class="k">def</span> <span class="nf">remove</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span>
        <span class="k">del</span> <span class="bp">self</span><span class="o">.</span><span class="n">dict</span><span class="p">[</span><span class="n">item</span><span class="p">]</span>

    <span class="k">def</span> <span class="nf">discard</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="n">item</span><span class="p">)</span>
        <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
            <span class="k">pass</span>

    <span class="k">def</span> <span class="nf">__iter__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="nb">iter</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">dict</span><span class="o">.</span><span class="n">keys</span><span class="p">())</span>

    <span class="k">def</span> <span class="nf">__contains__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span>
        <span class="k">return</span> <span class="n">item</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">dict</span>

    <span class="k">def</span> <span class="nf">__nonzero__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="nb">bool</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">dict</span><span class="p">)</span>


<span class="k">class</span> <span class="nc">MultiValueDictKeyError</span><span class="p">(</span><span class="ne">KeyError</span><span class="p">):</span>
    <span class="k">pass</span>


<span class="k">class</span> <span class="nc">MultiValueDict</span><span class="p">(</span><span class="nb">dict</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    A subclass of dictionary customized to handle multiple values for the</span>
<span class="sd">    same key.</span>

<span class="sd">    &gt;&gt;&gt; d = MultiValueDict({&#39;name&#39;: [&#39;Adrian&#39;, &#39;Simon&#39;], &#39;position&#39;: [&#39;Developer&#39;]})</span>
<span class="sd">    &gt;&gt;&gt; d[&#39;name&#39;]</span>
<span class="sd">    &#39;Simon&#39;</span>
<span class="sd">    &gt;&gt;&gt; d.getlist(&#39;name&#39;)</span>
<span class="sd">    [&#39;Adrian&#39;, &#39;Simon&#39;]</span>
<span class="sd">    &gt;&gt;&gt; d.getlist(&#39;doesnotexist&#39;)</span>
<span class="sd">    []</span>
<span class="sd">    &gt;&gt;&gt; d.getlist(&#39;doesnotexist&#39;, [&#39;Adrian&#39;, &#39;Simon&#39;])</span>
<span class="sd">    [&#39;Adrian&#39;, &#39;Simon&#39;]</span>
<span class="sd">    &gt;&gt;&gt; d.get(&#39;lastname&#39;, &#39;nonexistent&#39;)</span>
<span class="sd">    &#39;nonexistent&#39;</span>
<span class="sd">    &gt;&gt;&gt; d.setlist(&#39;lastname&#39;, [&#39;Holovaty&#39;, &#39;Willison&#39;])</span>

<span class="sd">    This class exists to solve the irritating problem raised by cgi.parse_qs,</span>
<span class="sd">    which returns a list for every key, even though most Web forms submit</span>
<span class="sd">    single name-value pairs.</span>
<span class="sd">    &quot;&quot;&quot;</span>
    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key_to_list_mapping</span><span class="o">=</span><span class="p">()):</span>
        <span class="nb">super</span><span class="p">(</span><span class="n">MultiValueDict</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">__init__</span><span class="p">(</span><span class="n">key_to_list_mapping</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="s">&quot;&lt;</span><span class="si">%s</span><span class="s">: </span><span class="si">%s</span><span class="s">&gt;&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">__class__</span><span class="o">.</span><span class="n">__name__</span><span class="p">,</span>
                             <span class="nb">super</span><span class="p">(</span><span class="n">MultiValueDict</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">__repr__</span><span class="p">())</span>

    <span class="k">def</span> <span class="nf">__getitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Returns the last data value for this key, or [] if it&#39;s an empty list;</span>
<span class="sd">        raises KeyError if not found.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="n">list_</span> <span class="o">=</span> <span class="nb">super</span><span class="p">(</span><span class="n">MultiValueDict</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">__getitem__</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>
        <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
            <span class="k">raise</span> <span class="n">MultiValueDictKeyError</span><span class="p">(</span><span class="nb">repr</span><span class="p">(</span><span class="n">key</span><span class="p">))</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="k">return</span> <span class="n">list_</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span>
        <span class="k">except</span> <span class="ne">IndexError</span><span class="p">:</span>
            <span class="k">return</span> <span class="p">[]</span>

    <span class="k">def</span> <span class="nf">__setitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span><span class="p">):</span>
        <span class="nb">super</span><span class="p">(</span><span class="n">MultiValueDict</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">__setitem__</span><span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="p">[</span><span class="n">value</span><span class="p">])</span>

    <span class="k">def</span> <span class="nf">__copy__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">__class__</span><span class="p">([</span>
            <span class="p">(</span><span class="n">k</span><span class="p">,</span> <span class="n">v</span><span class="p">[:])</span>
            <span class="k">for</span> <span class="n">k</span><span class="p">,</span> <span class="n">v</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">lists</span><span class="p">()</span>
        <span class="p">])</span>

    <span class="k">def</span> <span class="nf">__deepcopy__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">memo</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
        <span class="k">if</span> <span class="n">memo</span> <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span>
            <span class="n">memo</span> <span class="o">=</span> <span class="p">{}</span>
        <span class="n">result</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__class__</span><span class="p">()</span>
        <span class="n">memo</span><span class="p">[</span><span class="nb">id</span><span class="p">(</span><span class="bp">self</span><span class="p">)]</span> <span class="o">=</span> <span class="n">result</span>
        <span class="k">for</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span> <span class="ow">in</span> <span class="nb">dict</span><span class="o">.</span><span class="n">items</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
            <span class="nb">dict</span><span class="o">.</span><span class="n">__setitem__</span><span class="p">(</span><span class="n">result</span><span class="p">,</span> <span class="n">copy</span><span class="o">.</span><span class="n">deepcopy</span><span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="n">memo</span><span class="p">),</span>
                             <span class="n">copy</span><span class="o">.</span><span class="n">deepcopy</span><span class="p">(</span><span class="n">value</span><span class="p">,</span> <span class="n">memo</span><span class="p">))</span>
        <span class="k">return</span> <span class="n">result</span>

    <span class="k">def</span> <span class="nf">__getstate__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="n">obj_dict</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__dict__</span><span class="o">.</span><span class="n">copy</span><span class="p">()</span>
        <span class="n">obj_dict</span><span class="p">[</span><span class="s">&#39;_data&#39;</span><span class="p">]</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">((</span><span class="n">k</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">getlist</span><span class="p">(</span><span class="n">k</span><span class="p">))</span> <span class="k">for</span> <span class="n">k</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">obj_dict</span>

    <span class="k">def</span> <span class="nf">__setstate__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">obj_dict</span><span class="p">):</span>
        <span class="n">data</span> <span class="o">=</span> <span class="n">obj_dict</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="s">&#39;_data&#39;</span><span class="p">,</span> <span class="p">{})</span>
        <span class="k">for</span> <span class="n">k</span><span class="p">,</span> <span class="n">v</span> <span class="ow">in</span> <span class="n">data</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">setlist</span><span class="p">(</span><span class="n">k</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">__dict__</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">obj_dict</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">get</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">default</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Returns the last data value for the passed key. If key doesn&#39;t exist</span>
<span class="sd">        or value is an empty list, then default is returned.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="n">val</span> <span class="o">=</span> <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
        <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
            <span class="k">return</span> <span class="n">default</span>
        <span class="k">if</span> <span class="n">val</span> <span class="o">==</span> <span class="p">[]:</span>
            <span class="k">return</span> <span class="n">default</span>
        <span class="k">return</span> <span class="n">val</span>

    <span class="k">def</span> <span class="nf">getlist</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">default</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Returns the list of values for the passed key. If key doesn&#39;t exist,</span>
<span class="sd">        then a default value is returned.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="k">return</span> <span class="nb">super</span><span class="p">(</span><span class="n">MultiValueDict</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">__getitem__</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>
        <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
            <span class="k">if</span> <span class="n">default</span> <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span>
                <span class="k">return</span> <span class="p">[]</span>
            <span class="k">return</span> <span class="n">default</span>

    <span class="k">def</span> <span class="nf">setlist</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">list_</span><span class="p">):</span>
        <span class="nb">super</span><span class="p">(</span><span class="n">MultiValueDict</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">__setitem__</span><span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="n">list_</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">setdefault</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">default</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
        <span class="k">if</span> <span class="n">key</span> <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
            <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span> <span class="o">=</span> <span class="n">default</span>
            <span class="c"># Do not return default here because __setitem__() may store</span>
            <span class="c"># another value -- QueryDict.__setitem__() does. Look it up.</span>
        <span class="k">return</span> <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>

    <span class="k">def</span> <span class="nf">setlistdefault</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">default_list</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
        <span class="k">if</span> <span class="n">key</span> <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
            <span class="k">if</span> <span class="n">default_list</span> <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span>
                <span class="n">default_list</span> <span class="o">=</span> <span class="p">[]</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">setlist</span><span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="n">default_list</span><span class="p">)</span>
            <span class="c"># Do not return default_list here because setlist() may store</span>
            <span class="c"># another value -- QueryDict.setlist() does. Look it up.</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">getlist</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">appendlist</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Appends an item to the internal list associated with key.&quot;&quot;&quot;</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">setlistdefault</span><span class="p">(</span><span class="n">key</span><span class="p">)</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">value</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">_iteritems</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Yields (key, value) pairs, where value is the last item in the list</span>
<span class="sd">        associated with the key.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">for</span> <span class="n">key</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
            <span class="k">yield</span> <span class="n">key</span><span class="p">,</span> <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>

    <span class="k">def</span> <span class="nf">_iterlists</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Yields (key, list) pairs.&quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="n">six</span><span class="o">.</span><span class="n">iteritems</span><span class="p">(</span><span class="nb">super</span><span class="p">(</span><span class="n">MultiValueDict</span><span class="p">,</span> <span class="bp">self</span><span class="p">))</span>

    <span class="k">def</span> <span class="nf">_itervalues</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Yield the last value on every key list.&quot;&quot;&quot;</span>
        <span class="k">for</span> <span class="n">key</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
            <span class="k">yield</span> <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>

    <span class="k">if</span> <span class="n">six</span><span class="o">.</span><span class="n">PY3</span><span class="p">:</span>
        <span class="n">items</span> <span class="o">=</span> <span class="n">_iteritems</span>
        <span class="n">lists</span> <span class="o">=</span> <span class="n">_iterlists</span>
        <span class="n">values</span> <span class="o">=</span> <span class="n">_itervalues</span>
    <span class="k">else</span><span class="p">:</span>
        <span class="n">iteritems</span> <span class="o">=</span> <span class="n">_iteritems</span>
        <span class="n">iterlists</span> <span class="o">=</span> <span class="n">_iterlists</span>
        <span class="n">itervalues</span> <span class="o">=</span> <span class="n">_itervalues</span>

        <span class="k">def</span> <span class="nf">items</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
            <span class="k">return</span> <span class="nb">list</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">iteritems</span><span class="p">())</span>

        <span class="k">def</span> <span class="nf">lists</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
            <span class="k">return</span> <span class="nb">list</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">iterlists</span><span class="p">())</span>

        <span class="k">def</span> <span class="nf">values</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
            <span class="k">return</span> <span class="nb">list</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">itervalues</span><span class="p">())</span>

    <span class="k">def</span> <span class="nf">copy</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Returns a shallow copy of this object.&quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="n">copy</span><span class="o">.</span><span class="n">copy</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">update</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        update() extends rather than replaces existing key lists.</span>
<span class="sd">        Also accepts keyword args.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">args</span><span class="p">)</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s">&quot;update expected at most 1 arguments, got </span><span class="si">%d</span><span class="s">&quot;</span> <span class="o">%</span> <span class="nb">len</span><span class="p">(</span><span class="n">args</span><span class="p">))</span>
        <span class="k">if</span> <span class="n">args</span><span class="p">:</span>
            <span class="n">other_dict</span> <span class="o">=</span> <span class="n">args</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
            <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other_dict</span><span class="p">,</span> <span class="n">MultiValueDict</span><span class="p">):</span>
                <span class="k">for</span> <span class="n">key</span><span class="p">,</span> <span class="n">value_list</span> <span class="ow">in</span> <span class="n">other_dict</span><span class="o">.</span><span class="n">lists</span><span class="p">():</span>
                    <span class="bp">self</span><span class="o">.</span><span class="n">setlistdefault</span><span class="p">(</span><span class="n">key</span><span class="p">)</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="n">value_list</span><span class="p">)</span>
            <span class="k">else</span><span class="p">:</span>
                <span class="k">try</span><span class="p">:</span>
                    <span class="k">for</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span> <span class="ow">in</span> <span class="n">other_dict</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
                        <span class="bp">self</span><span class="o">.</span><span class="n">setlistdefault</span><span class="p">(</span><span class="n">key</span><span class="p">)</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">value</span><span class="p">)</span>
                <span class="k">except</span> <span class="ne">TypeError</span><span class="p">:</span>
                    <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="s">&quot;MultiValueDict.update() takes either a MultiValueDict or dictionary&quot;</span><span class="p">)</span>
        <span class="k">for</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span> <span class="ow">in</span> <span class="n">six</span><span class="o">.</span><span class="n">iteritems</span><span class="p">(</span><span class="n">kwargs</span><span class="p">):</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">setlistdefault</span><span class="p">(</span><span class="n">key</span><span class="p">)</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">value</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">dict</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Returns current object as a dict with singular values.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="nb">dict</span><span class="p">((</span><span class="n">key</span><span class="p">,</span> <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">])</span> <span class="k">for</span> <span class="n">key</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">)</span>


<span class="k">class</span> <span class="nc">ImmutableList</span><span class="p">(</span><span class="nb">tuple</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    A tuple-like object that raises useful errors when it is asked to mutate.</span>

<span class="sd">    Example::</span>

<span class="sd">        &gt;&gt;&gt; a = ImmutableList(range(5), warning=&quot;You cannot mutate this.&quot;)</span>
<span class="sd">        &gt;&gt;&gt; a[3] = &#39;4&#39;</span>
<span class="sd">        Traceback (most recent call last):</span>
<span class="sd">            ...</span>
<span class="sd">        AttributeError: You cannot mutate this.</span>
<span class="sd">    &quot;&quot;&quot;</span>

    <span class="k">def</span> <span class="nf">__new__</span><span class="p">(</span><span class="n">cls</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
        <span class="k">if</span> <span class="s">&#39;warning&#39;</span> <span class="ow">in</span> <span class="n">kwargs</span><span class="p">:</span>
            <span class="n">warning</span> <span class="o">=</span> <span class="n">kwargs</span><span class="p">[</span><span class="s">&#39;warning&#39;</span><span class="p">]</span>
            <span class="k">del</span> <span class="n">kwargs</span><span class="p">[</span><span class="s">&#39;warning&#39;</span><span class="p">]</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="n">warning</span> <span class="o">=</span> <span class="s">&#39;ImmutableList object is immutable.&#39;</span>
        <span class="bp">self</span> <span class="o">=</span> <span class="nb">tuple</span><span class="o">.</span><span class="n">__new__</span><span class="p">(</span><span class="n">cls</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">warning</span> <span class="o">=</span> <span class="n">warning</span>
        <span class="k">return</span> <span class="bp">self</span>

    <span class="k">def</span> <span class="nf">complain</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="o">*</span><span class="n">wargs</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">warning</span><span class="p">,</span> <span class="ne">Exception</span><span class="p">):</span>
            <span class="k">raise</span> <span class="bp">self</span><span class="o">.</span><span class="n">warning</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">AttributeError</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">warning</span><span class="p">)</span>

    <span class="c"># All list mutation functions complain.</span>
    <span class="n">__delitem__</span> <span class="o">=</span> <span class="n">complain</span>
    <span class="n">__delslice__</span> <span class="o">=</span> <span class="n">complain</span>
    <span class="n">__iadd__</span> <span class="o">=</span> <span class="n">complain</span>
    <span class="n">__imul__</span> <span class="o">=</span> <span class="n">complain</span>
    <span class="n">__setitem__</span> <span class="o">=</span> <span class="n">complain</span>
    <span class="n">__setslice__</span> <span class="o">=</span> <span class="n">complain</span>
    <span class="n">append</span> <span class="o">=</span> <span class="n">complain</span>
    <span class="n">extend</span> <span class="o">=</span> <span class="n">complain</span>
    <span class="n">insert</span> <span class="o">=</span> <span class="n">complain</span>
    <span class="n">pop</span> <span class="o">=</span> <span class="n">complain</span>
    <span class="n">remove</span> <span class="o">=</span> <span class="n">complain</span>
    <span class="n">sort</span> <span class="o">=</span> <span class="n">complain</span>
    <span class="n">reverse</span> <span class="o">=</span> <span class="n">complain</span>


<span class="k">class</span> <span class="nc">DictWrapper</span><span class="p">(</span><span class="nb">dict</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    Wraps accesses to a dictionary so that certain values (those starting with</span>
<span class="sd">    the specified prefix) are passed through a function before being returned.</span>
<span class="sd">    The prefix is removed before looking up the real value.</span>

<span class="sd">    Used by the SQL construction code to ensure that values are correctly</span>
<span class="sd">    quoted before being used.</span>
<span class="sd">    &quot;&quot;&quot;</span>
    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">data</span><span class="p">,</span> <span class="n">func</span><span class="p">,</span> <span class="n">prefix</span><span class="p">):</span>
        <span class="nb">super</span><span class="p">(</span><span class="n">DictWrapper</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">__init__</span><span class="p">(</span><span class="n">data</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">func</span> <span class="o">=</span> <span class="n">func</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">prefix</span> <span class="o">=</span> <span class="n">prefix</span>

    <span class="k">def</span> <span class="nf">__getitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Retrieves the real value after stripping the prefix string (if</span>
<span class="sd">        present). If the prefix is present, pass the value through self.func</span>
<span class="sd">        before returning, otherwise return the raw value.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">if</span> <span class="n">key</span><span class="o">.</span><span class="n">startswith</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">prefix</span><span class="p">):</span>
            <span class="n">use_func</span> <span class="o">=</span> <span class="bp">True</span>
            <span class="n">key</span> <span class="o">=</span> <span class="n">key</span><span class="p">[</span><span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">prefix</span><span class="p">):]</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="n">use_func</span> <span class="o">=</span> <span class="bp">False</span>
        <span class="n">value</span> <span class="o">=</span> <span class="nb">super</span><span class="p">(</span><span class="n">DictWrapper</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">__getitem__</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>
        <span class="k">if</span> <span class="n">use_func</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">func</span><span class="p">(</span><span class="n">value</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">value</span>
</pre></div>

          </div>
        </div>
      </div>
      
        
          <div class="yui-b" id="sidebar">
            
      <div class="sphinxsidebar">
        <div class="sphinxsidebarwrapper">
  <h3>Browse</h3>
  <ul>
    
    
  </ul>
  <h3>You are here:</h3>
  <ul>
      <li>
        <a href="../../../index.html">Django 1.7.8.dev20150401230226 documentation</a>
        
          <ul><li><a href="../../index.html">Module code</a>
        
          <ul><li><a href="../../django.html">django</a>
        
        <ul><li>django.utils.datastructures</li></ul>
        </li></ul></li></ul>
      </li>
  </ul>

<div id="searchbox" style="display: none">
  <h3>Quick search</h3>
    <form class="search" action="../../../search.html" method="get">
      <input type="text" name="q" />
      <input type="submit" value="Go" />
      <input type="hidden" name="check_keywords" value="yes" />
      <input type="hidden" name="area" value="default" />
    </form>
    <p class="searchtip" style="font-size: 90%">
    Enter search terms or a module, class or function name.
    </p>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>
              <h3>Last update:</h3>
              <p class="topless">Apr 02, 2015</p>
          </div>
        
      
    </div>

    <div id="ft">
      <div class="nav">
    <a href="../../index.html" title="Module code" accesskey="U">up</a></div>
    </div>
  </div>

      <div class="clearer"></div>
    </div>
  </body>
</html>